package leetcode.f1t100;

/**
 * nums字典序排列的下一个排序
 * https://leetcode.com/problems/next-permutation/
 *
 * @Author lichongxiao
 * @Date 2022/10/9 9:21
 */
public class Q31_NextPermutation {
    public void nextPermutation(int[] nums) {
        int length = nums.length, i = length - 2, j = length - 1;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if(i>=0){
            while(nums[j]<=nums[i]){
                j--;
            }
            swap(nums,i,j);
        }
        i++;
        j = length -1;
        while(i < j){
            swap(nums,i,j);
            i++;
            j--;
        }
    }
    public void swap(int[] nums, int i, int j){
        nums[i] += nums[j];
        nums[j] = nums[i] - nums[j];
        nums[i] -= nums[j];
    }

    public static void main(String[] args) {
        int[] nums = new int[]{7,9,8,6,5};
        new Q31_NextPermutation().nextPermutation(nums);
        for(int num : nums){
            System.out.println(num);
        }
    }
}
